'''
LEETCODE - WORD SEARCH II
给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
同一个单元格内的字母在一个单词中不允许被重复使用。

示例:
输入: 
words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

输出: ["eat","oath"]
说明:
你可以假设所有输入都由小写字母 a-z 组成。

提示:
你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？
如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： 实现Trie（前缀树）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search-ii
'''
# 方法一： 对words 进行遍历 --> board search
#           时间复杂度： O(N*m*m*4^k) N:单词个数 m:二维网格边长 4:下个字符的四个通路 k:单词长度
#方法二 ： Trie
#1. all words --> Trie 构建起字典树 （prefix
#2. borad DFS
#时间复杂度
#

END_OF_WORD = "#"
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        if not board or not board[0]:return[]
        if not words: return[]
        self.result = set()

        #建构Trie
        root = collections.defaultdict()
        for word in words:
            node = root
            for char in word:
                node = node.setdefault(char,collections.defaultdict())
            node[END_OF_WORD] = END_OF_WORD
        
        self.m,self.n = len(board),len(board[0])
        for i in xrange(self.m):
            for j in yrange(self.n):
                if board[i][j] in root:
                    self.__dfs(board,i,j,"",root)
        return list(self.result)